package com.cjl.dmsxl.array;

import org.junit.jupiter.api.Test;

public class ArrayPractice {
    /**
     * 704. 二分查找
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        // 范围判断
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        // 左闭右闭原则
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 977. 有序数组的平方
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        // 双指针
        int left = 0;
        int right = nums.length - 1;
        // 新数组
        int[] res = new int[nums.length];
        int index = res.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                res[index] = nums[left] * nums[left];
                left++;
            } else {
                res[index] = nums[right] * nums[right];
                right--;
            }
            index--;
        }
        return res;
    }

    /**
     * 209. 长度最小的子数组
     *
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        // 定义结果
        int res = Integer.MAX_VALUE;
        // 定义滑动窗口起始位置
        int start = 0;
        // 定义滑动窗口中的元素和
        int sum = 0;
        // 定义滑动窗口长度
        int minLength = 0;
        // 第一层循环查找滑动窗口终止位置
        for (int end = 0; end < nums.length; end++) {
            // 累加终止位置的元素值
            sum += nums[end];
            // 当元素和大于等于目标值的时候开始收集结果
            // 判断并更新滑动窗口起始位置,当sum >= target的时候则开始收集结果
            while (sum >= target) {
                // 获取子序列长度
                minLength = end - start + 1;
                // 更新结果
                res = Math.min(res, minLength);
                // 移动窗口起始位置并减去元素和
                sum -= nums[start++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    /**
     * 59. 螺旋矩阵 II
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int loop = 0;  // 控制循环次数
        int[][] res = new int[n][n];
        int start = 0;  // 每次循环的开始点(start, start)
        int count = 1;  // 定义填充数字
        int i, j;
        while (loop++ < n / 2) { // 判断边界后，loop从1开始
            // 模拟上侧从左到右
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }
            // 模拟右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }
            // 模拟下侧从右到左
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }
            // 模拟左侧从下到上
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++;
        }
        if (n % 2 == 1) {
            res[start][start] = count;
        }
        return res;
    }

    @Test
    void test() {
        generateMatrix(3);
    }

}
